/**
 * Created with IntelliJ IDEA.
 * Description:
 * 给定一个头节点为head的非空单链表，返回链表的中间节点
 * 如果有俩个中间节点，返回第二个中间节点
 * User: xwl
 */

class ListNode2 {
    int val;
    ListNode2 next;
    ListNode2() {}
    ListNode2(int val) { this.val = val; }
    ListNode2(int val, ListNode2 next) { this.val = val; this.next = next; }
}

public class Test4 {
    public ListNode2 middleNode(ListNode2 head) {
        // 定义俩个指针，分别为快慢指针
        ListNode2 quickNode = head;
        ListNode2 slowNode = head;
        // 判断特殊情况
        if (head == null) {
            return null;
        }
        // 实现
        while (quickNode != null && quickNode.next != null) {
            // 快指针走俩步，满指针走一步
            quickNode = quickNode.next.next;
            slowNode = slowNode.next;
        }
        // 返回慢指针
        return slowNode;
    }
}
